695. Max Area of Island

Question

You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Example 1:

Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directonally.

Example 2:

Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• grid[i][j] is either 0 or 1.

---

Approach

Recursive

1. Create a boolean vector with the same size as grid, this will be used when we iterate through cells.
2. For each cell in the grid, we check the total area that is interconnected.
3. If the cell is 0, area is simply 0. Mark the cell as checked in the boolean vector.
4. Otherwise, increment the total area by checking, if any, the left / right / top / bottom cells of the current cell, and mark them as well.
5. E.g. If the left cell of current cell has a neighbour, we will check that as well and increment the area. Rinse and repeat.
6. Stop when all the neighbours of cells that are 1 are marked as check.
7. Return the maximum area after checking the whole grid.

Solution

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        //empty grid to record flag
        vector<vector<bool>> flag(grid.size(),vector<bool> (grid[0].size()));
        int maxArea = 0;
        
        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[0].size(); j++){
                maxArea = max(maxArea,checkCells(grid,flag,i,j));
            }
        }
        return maxArea;
    }
    
    int checkCells(vector<vector<int>>& grid, vector<vector<bool>>& flag,int i, int j){
        if(flag[i][j]) return 0;
        else flag[i][j] = true;
        
        int area = 0;
        
        if(grid[i][j] > 0) area = 1;
        else return 0;
        
        //left
        if(i > 0) area += checkCells(grid,flag,i - 1,j);
        
        //right
        if(i < grid.size() - 1) area += checkCells(grid,flag,i + 1,j);
        
        //up
        if(j > 0) area += checkCells(grid,flag,i,j - 1);
        
        //down
        if(j < grid[0].size() - 1) area += checkCells(grid,flag,i,j + 1);
        
        return area;
    }
};